package com.lsa.letcode.the62.uniquePath;

public class Solution {
	public int uniquePaths(int r, int c) {
		int size = r - 1 + c - 1;
		return C_n_k(size, r - 1);
	}
	
	private static int C_n_k(int n, int k) {
		int[][] C_n_k = new int[n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
			C_n_k[i][0] = 1;
		}
		for (int i = 1; i <= n; i++) {
			C_n_k[i][i] = 1;
		}
		
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= i; j++) {
				C_n_k[i][j] = C_n_k[i - 1][j - 1]  + C_n_k[i - 1][j];
				if (i == n && j == k) {
					return C_n_k[i][j];
				}
			}
		}
		return C_n_k[n][k];
	}
}